package developer.排序算法.快速排序;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {99, 55, 2, 3, 9, 10, 22, 34, 67, 89, 69, 92, 101, 102};
        //定义队首位置的索引
        int left = 0;
        //定义队尾位置的索引
        int right = arr.length - 1;
        sort(arr, left, right);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            //定义基准数
            int pivot = arr[left];
            //记录序列的开始
            int begin = left;
            //记录序列的结束
            int end = right;

            while (right > left) {
                //当队尾元素小于基准数就将队尾插到队首
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    //并将队首索引后移
                    left++;
                } else {
                    //当队尾元素大于基准数就将队尾索引前移
                    //并继续从队尾比较
                    right--;
                    continue;
                }
                while (right > left) {
                    //当队首元素大于基准数就将队首位置插到队尾
                    if (arr[left] > pivot) {
                        arr[right] = arr[left];
                        //并将队尾索引前移
                        right--;
                        break;
                    } else {
                        //当队首元素小于基准数就将队首索引前移
                        //并继续从队首比较
                        left++;
                    }
                }
            }
            //队首和队尾索引重合，就将基准数插入此位置
            arr[left] = pivot;

            sort(arr, begin, left - 1);
            sort(arr, left + 1, end);
        }
    }
}